home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / gnu / groff108.lha / groff-1.08 / include / ptable.h < prev    next >
C/C++ Source or Header  |  1992-08-25  |  5KB  |  167 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21. #include <assert.h>
  22. #include <string.h>
  23.  
  24. #ifdef TRADITIONAL_CPP
  25. #define name2(a,b) a/**/b
  26. #else /* not TRADITIONAL_CPP */
  27. #define name2(a,b) name2x(a,b)
  28. #define name2x(a,b) a ## b
  29. #endif /* not TRADITIONAL_CPP */
  30.  
  31. #define PTABLE(T) name2(T,_ptable)
  32. #define PASSOC(T) name2(T,_passoc)
  33. #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  34.  
  35. extern unsigned next_ptable_size(unsigned);
  36. extern unsigned long hash_string(const char *);
  37.  
  38. #define declare_ptable(T)                              \
  39.                                           \
  40. struct PASSOC(T) {                                  \
  41.   char *key;                                            \
  42.   T *val;                                      \
  43.   PASSOC(T)();                                      \
  44. };                                          \
  45.                                           \
  46. struct PTABLE(T);                                  \
  47.                                           \
  48. class PTABLE_ITERATOR(T) {                              \
  49.   PTABLE(T) *p;                                      \
  50.   unsigned i;                                      \
  51. public:                                          \
  52.   PTABLE_ITERATOR(T)(PTABLE(T) *);                          \
  53.   int next(const char **, T **);                          \
  54. };                                          \
  55.                                           \
  56. class PTABLE(T) {                                  \
  57.   PASSOC(T) *v;                                      \
  58.   unsigned size;                                  \
  59.   unsigned used;                                  \
  60.   enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 };              \
  61. public:                                          \
  62.   PTABLE(T)();                                      \
  63.   ~PTABLE(T)();                                      \
  64.   void define(const char *, T *);                          \
  65.   T *lookup(const char *);                              \
  66.   friend class PTABLE_ITERATOR(T);                          \
  67. };
  68.  
  69.  
  70. #define implement_ptable(T)                              \
  71.                                           \
  72. PASSOC(T)::PASSOC(T)()                                  \
  73. : key(0), val(0)                                  \
  74. {                                          \
  75. }                                          \
  76.                                           \
  77. PTABLE(T)::PTABLE(T)()                                  \
  78. {                                          \
  79.   v = new PASSOC(T)[size = INITIAL_SIZE];                      \
  80.   used = 0;                                      \
  81. }                                          \
  82.                                           \
  83. PTABLE(T)::~PTABLE(T)()                                  \
  84. {                                          \
  85.   for (unsigned i = 0; i < size; i++) {                          \
  86.     a_delete v[i].key;                                  \
  87.     delete v[i].val;                                  \
  88.   }                                          \
  89.   a_delete v;                                      \
  90. }                                          \
  91.                                           \
  92. void PTABLE(T)::define(const char *key, T *val)                      \
  93. {                                          \
  94.   assert(key != 0);                                  \
  95.   unsigned long h = hash_string(key);                          \
  96.   for (unsigned n = unsigned(h % size);                          \
  97.        v[n].key != 0;                                  \
  98.        n = (n == 0 ? size - 1 : n - 1))                          \
  99.     if (strcmp(v[n].key, key) == 0) {                          \
  100.       delete v[n].val;                                  \
  101.       v[n].val = val;                                  \
  102.       return;                                      \
  103.     }                                          \
  104.   if (val == 0)                                      \
  105.     return;                                      \
  106.   if (used*FULL_DEN >= size*FULL_NUM) {                          \
  107.     PASSOC(T) *oldv = v;                              \
  108.     unsigned old_size = size;                              \
  109.     size = next_ptable_size(size);                          \
  110.     v = new PASSOC(T)[size];                              \
  111.     for (unsigned i = 0; i < old_size; i++)                      \
  112.       if (oldv[i].key != 0) {                              \
  113.     if (oldv[i].val == 0)                              \
  114.       a_delete oldv[i].key;                              \
  115.     else {                                      \
  116.       for (unsigned j = unsigned(hash_string(oldv[i].key) % size);          \
  117.            v[j].key != 0;                              \
  118.            j = (j == 0 ? size - 1 : j - 1))                      \
  119.          ;                                  \
  120.       v[j].key = oldv[i].key;                          \
  121.       v[j].val = oldv[i].val;                          \
  122.     }                                      \
  123.       }                                          \
  124.     for (n = unsigned(h % size);                          \
  125.      v[n].key != 0;                                  \
  126.      n = (n == 0 ? size - 1 : n - 1))                      \
  127.       ;                                          \
  128.     a_delete oldv;                                  \
  129.   }                                          \
  130.   char *temp = new char[strlen(key)+1];                          \
  131.   strcpy(temp, key);                                  \
  132.   v[n].key = temp;                                  \
  133.   v[n].val = val;                                  \
  134.   used++;                                      \
  135. }                                          \
  136.                                           \
  137. T *PTABLE(T)::lookup(const char *key)                          \
  138. {                                          \
  139.   assert(key != 0);                                  \
  140.   for (unsigned n = unsigned(hash_string(key) % size);                  \
  141.        v[n].key != 0;                                  \
  142.        n = (n == 0 ? size - 1 : n - 1))                          \
  143.     if (strcmp(v[n].key, key) == 0)                          \
  144.       return v[n].val;                                  \
  145.   return 0;                                      \
  146. }                                          \
  147.                                           \
  148. PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                  \
  149. : p(t), i(0)                                      \
  150. {                                          \
  151. }                                          \
  152.                                           \
  153. int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)              \
  154. {                                          \
  155.   unsigned size = p->size;                              \
  156.   PASSOC(T) *v = p->v;                                  \
  157.   for (; i < size; i++)                                  \
  158.     if (v[i].key != 0) {                              \
  159.       *keyp = v[i].key;                                  \
  160.       *valp = v[i].val;                                  \
  161.       i++;                                      \
  162.       return 1;                                      \
  163.     }                                          \
  164.   return 0;                                      \
  165. }
  166.  
  167.